//////////给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。 
//////////
////////// 
////////// 
//////////
////////// 
//////////
////////// 示例 1： 
//////////
////////// 
//////////输入：nums = [-4,-1,0,3,10]
//////////输出：[0,1,9,16,100]
//////////解释：平方后，数组变为 [16,1,0,9,100]
//////////排序后，数组变为 [0,1,9,16,100] 
//////////
////////// 示例 2： 
//////////
////////// 
//////////输入：nums = [-7,-3,2,3,11]
//////////输出：[4,9,9,49,121]
////////// 
//////////
////////// 
//////////
////////// 提示： 
//////////
////////// 
////////// 1 <= nums.length <= 10⁴ 
////////// -10⁴ <= nums[i] <= 10⁴ 
////////// nums 已按 非递减顺序 排序 
////////// 
//////////
////////// 
//////////
////////// 进阶： 
//////////
////////// 
////////// 请你设计时间复杂度为 O(n) 的算法解决本问题 
////////// 
////////// Related Topics 数组 双指针 排序 👍 466 👎 0
////////
//////
////
//

package leetcode.editor.cn;

class SquaresOfASortedArray {
    public static void main(String[] args) {
        Solution solution = new SquaresOfASortedArray().new Solution();
        solution.sortedSquares(new int[]{-5, -3, -2, -1});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] sortedSquares(int[] nums) {
            // 解法一
            // int index = 0;
            // for (int i = 0; i < nums.length; i++) {
            //     nums[index++] = nums[i] * nums[i];
            // }
            // // 使用sort自动排序
            // Arrays.sort(nums);
            // return nums;


            // 双指针解法二
            /*int index = nums.length - 1, left = 0, right = nums.length - 1;
            int[] result = new int[nums.length];
            while (left <= right) {
                if (nums[left] * nums[left] > nums[right] * nums[right]) {
                    result[index--] = nums[left] * nums[left];
                    left++;
                } else {
                    result[index--] = nums[right] * nums[right];
                    right--;
                }
            }
            return result;*/

            // TODO 左右双指针
            /*int leftIndex = 0, rightIndex = nums.length - 1;
            int index = nums.length - 1;
            int[] result = new int[nums.length]; // 结果集
            while (leftIndex <= rightIndex) {
                if (nums[leftIndex] * nums[leftIndex] > nums[rightIndex] * nums[rightIndex]) {
                    result[index--] = nums[leftIndex] * nums[leftIndex];  // 大的放在结果集后边
                    leftIndex++;
                } else {
                    result[index--] = nums[rightIndex] * nums[rightIndex];  // 大的放在结果集后边
                    rightIndex++;
                }
            }
            return result;*/

            int n = nums.length;
            int l = 0, r = n - 1, k = n - 1;
            int[] res = new int[n];
            while (l < r) {
                int a = nums[l] * nums[l];
                int b = nums[r] * nums[r];
                if (a <= b) {
                    res[k--] = b;
                    r--;
                } else {
                    res[k--] = a;
                    l++;
                }
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
